package middle;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class Solution_264 {

    public static void main(String[] args) {
        Solution_264 model = new Solution_264();
        System.out.println(model.nthUglyNumber(10));
        System.out.println(model.nthUglyNumber(1));
    }

    public int nthUglyNumber(int n) {
        Set<Long> exist = new HashSet<>();
        PriorityQueue<Long> queue = new PriorityQueue<>();
        queue.add(1L);
        Long num = null;
        while (n > 0) {
            num = queue.poll();
            System.out.print(num + ";");
            long next = 2 * num;
            if (!exist.contains(next)) {
                queue.add(next);
                exist.add(next);
            }
            next = 3 * num;
            if (!exist.contains(next)) {
                queue.add(next);
                exist.add(next);
            }
            next = 5 * num;
            if (!exist.contains(next)) {
                queue.add(next);
                exist.add(next);
            }
            n--;
        }
        return num.intValue();
    }
}
